package Subject;

/**
 * 难度：中等
 * 
 * 316. 去除重复字母
 * 	给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小
 * 	（要求不能打乱其他字符的相对位置）。
 * 	注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence
 * 	-of-distinct-characters 相同
 * 
 * 示例 1：
 * 	输入：s = "bcabc"
 * 	输出："abc"
 * 示例 2：
 * 	输入：s = "cbacdcbc"
 * 	输出："acdb"
 * 
 * 提示：
 * 	1 <= s.length <= 104
 * 	s 由小写英文字母组成
 *
 * */

public class RemoveDuplicateLetters {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		RemoveDuplicateLetters rdl = new RemoveDuplicateLetters();
		System.out.println(rdl.removeDuplicateLetters("cbacdcbc"));
	}
	//方法一：贪心 + 栈
	public String removeDuplicateLetters(String s) {
		//判断字符是否出现过
		boolean[] vis=new boolean[26];
		//记录字符重复次数
		int[] num=new int[26];
		for(int i=0;i<s.length();i++) {
			num[s.charAt(i)-'a']++;
		}
		
		StringBuffer sb = new StringBuffer();
		for(int i=0;i<s.length();i++) {
			char ch = s.charAt(i);
			//如果重复，那么直接跳过
			if(!vis[ch-'a']) {
				//如果字符串长度大于0并且字符串最后一位大于当前字符，进入内循环
				while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
					//如果字符串中最后一位字符重复次数大于0，那么删除该字符，否则跳出内循环
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
				vis[ch-'a']=true;
				sb.append(s.charAt(i));
			}
			num[ch-'a']-=1;
		}
		return sb.toString();
	}
}
